1. Field of the Invention
The present invention is directed generally to an apparatus and method for solving packing and component layout problems.
2. Description of the Background
Several research efforts have been directed to the solution of component layout problems wherein the components must be located in such a fashion that certain spatial constraints are satisfied. These spatial constraints often consist of orientation, proximity, or overlap conditions, among others.
Numerous approaches have been presented to overcome the inherent problems of layout under such constraints. The operations research approach, often evidenced in packing problem solutions, typically presents a layout which cannot account for various types of spatial constraints and complex geometries. The ability to adjust to such constraints is vital if a solution is to be applied to general engineering problems, particularly in three dimensions.
The optimization approach frequently used to simulate a three dimensional component layout situation represents a non-linear approach. That approach gives rise to another set of difficulties: feasible starting points are required, linear approximations are used for non-linear equations, or highly complex mathematical operations, such as gradients, must be used, leading to a greater chance of error and local convergence.
Other approaches have been developed to overcome component layout problems. One of the most widely used new approaches, both in academics and in industry, is the simulated annealing algorithm. That technique overcomes some of the difficulties presented by complex geometries or restrictions on spatial movements. In the simulated annealing optimization technique, an initial state is chosen as a starting point and evaluated. A random step is then taken and evaluated, and, if the step has improved the value of the objective function (the mathematical representation of the goals and series of constraints to which the design is subject), that step is chosen as the new current design state.
If the step leads to an inferior design state, it is assigned a probability. That probability is a function of a decreasing parameter called "temperature," based on an analogy with the annealing of metals. The temperature parameter allows for a very broad view of the objective function layout space at the starting condition, and allows the algorithm to eventually converge on the most promising areas of the objective function as time progresses. It is this convergence on only the most promising areas of the objective function which allows this technique to partially remedy a great problem in component layout objective function problems--convergence on a local, rather than a global, optimum. However, depending on the complexity of the geometric model used, calculation time for this method could be quite lengthy.
Yet another approach has added the use of a plurality of models to the simulated annealing method. This approach uses simplistic geometric models early in the simulated anneal when large step sizes are likely to be used for high temperatures. Later in the process, complex geometric models are used when mostly small steps are being taken at low temperatures. Such variation in models improved calculation time to some degree, and allowed for optimization in three dimensions.
Pattern direct search algorithms are a subset of direct search algorithms introduced in Hooke, R., et al., "Direct Search Solution of Numerical and Statistical Problems," Journal of the Association for Computing Machinery, 8(2): 212-29, 1961, which is herein incorporated by reference. Hooke describes various parameters that are varied in pattern based search algorithms. Pattern direct search algorithms, which were used to solve curve fitting problems, follow a series of exploratory moves defined by pattern matrices to walk through a design space to search for a stationary point. The algorithms rely on direct comparisons of function values during the search, and thus provide a suitable tool for the exploration of a nonlinear and combinatorial design space.
However, the central problem of the objective function settling on an inferior local optimum still exists even with these techniques. Furthermore, due to the number of calculations needed, the running times of even the fastest of these optimization methods are still problematic. Thus, the need exists for a method that provides the advantages of a pattern based technique with its ability to handle complex geometries and constraints, while preventing convergence on an inferior local optimum, and yet reduces the calculation time for the optimization.